package list;
/**
 * @Classname RerseList
 * @Description TODO
 * @Date 2021/5/10 21:07
 * @Created by 张斌
 */
public class RerseList {
    public static class Node<T>{
        public T t;
        public Node<T> next;

        public Node(T t, Node<T> next) {
            this.t = t;
            this.next = next;
        }
    }

    public static void main(String[] args) {
            Node<Integer> node6=new Node<Integer>(6,null);
            Node<Integer> node5=new Node<Integer>(5,node6);
            Node<Integer> node4=new Node<Integer>(4,node5);
            Node<Integer> node3=new Node<Integer>(3,node4);
            Node<Integer> node2=new Node<Integer>(2,node3);
            Node<Integer> node1=new Node<Integer>(1,node2);
            Node<Integer> nodeCur=  reverse2(node1);
            while(nodeCur!=null){
                System.out.println(nodeCur.t);
                nodeCur=nodeCur.next;
            }
        //System.out.println(nodeCur.t);
    }
    /**
     * 迭代进行链表反转，需要用三个变量:nodeCur,nodeNext,nodePre
     * nodeCur指向当前要操作的节点，
     * nodeNext保存当前节点的后继节点，
     * nodePre指向已经反转后的链表，开始时设为null
     * */
    public static <T> Node<T> reverse(Node<T> node){
        if(null==node||null==node.next){
            return node;
        }
        Node<T> nodeCur=node;
        Node<T> nodeNext,nodePre=null;
        while(nodeCur!=null){
            nodeNext=nodeCur.next;
            nodeCur.next=nodePre;
            nodePre=nodeCur;
            nodeCur=nodeNext;
        }
        return nodePre;
    }
    /**
     * 迭代进行链表反转，需要用三个变量:nodeCur,nodeNext,nodePre
     * node:指向当前要操作的节点，方法参数，可以少声明一个变量
     * nodeNext保存当前节点的后继节点，
     * nodePre指向已经反转后的链表，开始时设为null
     * */
    public static <T> Node<T> reverse2(Node<T> node){
        if(null==node||null==node.next){
            return node;
        }
       // Node<T> nodeCur=node;
        Node<T> nodeNext,nodePre=null;
        while(node!=null){
            nodeNext=node.next;
            node.next=nodePre;
            nodePre=node;
            node=nodeNext;
        }
        return nodePre;
    }
    /**
     * 递归反转链表
     * 1→2→3→4→5→6
     * 6→5→4→3→2→1
     *
     *
     * 找到最后一个节点，
     * 第一步，反转head和之后的节点： head.next.next=head;
     *                              head.next=null;
     *  第二步，递归调用自己，找到最后一个节点，recursion(head.next)
     *  第三步，递归的截止条件if(null==head||null==head.next){
     *                              return head;
     *                      }
     * */
    public static<T> Node<T> recursion(Node<T> head){
        if(null==head||null==head.next){
            return head;
        }
        Node new_Head=recursion(head.next);
        head.next.next=head;
        head.next=null;
        return new_Head;
    }

}
